// Adapted from THREE.TypedArrayUtils (https://github.com/mrdoob/three.js/blob/dev/examples/js/TypedArrayUtils.js)

var BinaryHeap = require('ds/BinaryHeap');

/**
 * In-place quicksort for typed arrays (e.g. for Float32Array)
 * provides fast sorting
 * useful e.g. for a custom shader and/or BufferGeometry
 *
 * @author Roman Bolzern <roman.bolzern@fhnw.ch>, 2013
 * @author I4DS http://www.fhnw.ch/i4ds, 2013
 * @license MIT License <http://www.opensource.org/licenses/mit-license.php>
 *
 * Complexity: http://bigocheatsheet.com/ see Quicksort
 *
 * Example:
 * points: [x, y, z, x, y, z, x, y, z, ...]
 * eleSize: 3 //because of (x, y, z)
 * orderElement: 0 //order according to x
 * @private
 */

function quicksortInPlace( arr, eleSize, orderElement ) {
  var stack = [];
  var sp = - 1;
  var left = 0;
  var right = arr.length / eleSize - 1;
  var tmp = 0.0, x = 0, y = 0;

  var swapF = function ( a, b ) {
    a *= eleSize; b *= eleSize;
    for ( y = 0; y < eleSize; y ++ ) {
      tmp = arr[ a + y ];
      arr[ a + y ] = arr[ b + y ];
      arr[ b + y ] = tmp;
    }
  };

  var i, j, swap = new Float32Array( eleSize ), temp = new Float32Array( eleSize );
  while ( true ) {
    if ( right - left <= 25 ) {
      for ( j = left + 1; j <= right; j ++ ) {
        for ( x = 0; x < eleSize; x ++ ) {
          swap[ x ] = arr[ j * eleSize + x ];
        }

        i = j - 1;
        while ( i >= left && arr[ i * eleSize + orderElement ] > swap[ orderElement ] ) {
          for ( x = 0; x < eleSize; x ++ ) {
            arr[ ( i + 1 ) * eleSize + x ] = arr[ i * eleSize + x ];
          }
          i --;
        }

        for ( x = 0; x < eleSize; x ++ ) {
          arr[ ( i + 1 ) * eleSize + x ] = swap[ x ];
        }
      }

      if ( sp == - 1 ) break;

      right = stack[ sp -- ]; //?
      left = stack[ sp -- ];
    } else {
      var median = ( left + right ) >> 1;
      i = left + 1;
      j = right;
      swapF( median, i );

      if ( arr[ left * eleSize + orderElement ] > arr[ right * eleSize + orderElement ] ) {
        swapF( left, right );
      }

      if ( arr[ i * eleSize + orderElement ] > arr[ right * eleSize + orderElement ] ) {
        swapF( i, right );
      }

      if ( arr[ left * eleSize + orderElement ] > arr[ i * eleSize + orderElement ] ) {
        swapF( left, i );
      }

      for ( x = 0; x < eleSize; x ++ ) {
        temp[ x ] = arr[ i * eleSize + x ];
      }

      while ( true ) {
        do i ++; while ( arr[ i * eleSize + orderElement ] < temp[ orderElement ] );
        do j --; while ( arr[ j * eleSize + orderElement ] > temp[ orderElement ] );
        if ( j < i ) break;
        swapF( i, j );
      }

      for ( x = 0; x < eleSize; x ++ ) {
        arr[ ( left + 1 ) * eleSize + x ] = arr[ j * eleSize + x ];
        arr[ j * eleSize + x ] = temp[ x ];
      }
      if ( right - i + 1 >= j - left ) {
        stack[ ++ sp ] = i;
        stack[ ++ sp ] = right;
        right = j - 1;
      } else {
        stack[ ++ sp ] = left;
        stack[ ++ sp ] = j - 1;
        left = i;
      }
    }
  }
  return arr;
}

/**
 * k-d Tree for typed arrays (e.g. for Float32Array), in-place
 * provides fast nearest neighbour search
 * useful e.g. for a custom shader and/or BufferGeometry, saves tons of memory
 * has no insert and remove, only buildup and neares neighbour search
 *
 * Based on https://github.com/ubilabs/kd-tree-javascript by Ubilabs
 *
 * @author Roman Bolzern <roman.bolzern@fhnw.ch>, 2013
 * @author I4DS http://www.fhnw.ch/i4ds, 2013
 * @license MIT License <http://www.opensource.org/licenses/mit-license.php>
 *
 * Requires typed array quicksort
 *
 * Example:
 * points: [x, y, z, x, y, z, x, y, z, ...]
 * metric: function(a, b){	return Math.pow(a[0] - b[0], 2) +  Math.pow(a[1] - b[1], 2) +  Math.pow(a[2] - b[2], 2); }  //Manhatten distance
 * eleSize: 3 //because of (x, y, z)
 *
 * Further information (including mathematical properties)
 * http://en.wikipedia.org/wiki/Binary_tree
 * http://en.wikipedia.org/wiki/K-d_tree
 *
 * If you want to further minimize memory usage, remove Node.depth and replace in search algorithm with a traversal to root node (see comments at THREE.TypedArrayUtils.Kdtree.prototype.Node)
 * @constructor
 * @memberOf ds
 */

var KDTree = function ( points, metric, eleSize ) {
  var self = this;
  var maxDepth = 0;

  var getPointSet = function ( points, pos ) {
    return points.subarray( pos * eleSize, pos * eleSize + eleSize );
  };

  function buildTree( points, depth, parent, pos ) {
    var dim = depth % eleSize,
      median,
      node,
      plength = points.length / eleSize;

    if ( depth > maxDepth ) maxDepth = depth;

    if ( plength === 0 ) return null;
    if ( plength === 1 ) {
      return new self.Node( getPointSet( points, 0 ), depth, parent, pos );
    }

    quicksortInPlace( points, eleSize, dim );
    median = Math.floor( plength / 2 );
    node = new self.Node( getPointSet( points, median ), depth, parent, median + pos );
    node.left = buildTree( points.subarray( 0, median * eleSize ), depth + 1, node, pos );
    node.right = buildTree( points.subarray( ( median + 1 ) * eleSize, points.length ), depth + 1, node, pos + median + 1 );
    return node;
  }

  this.root = buildTree( points, 0, null, 0 );

  this.getMaxDepth = function () {
    return maxDepth;
  };

  this.nearest = function ( point, maxNodes, maxDistance ) {

    /* point: array of size eleSize
     maxNodes: max amount of nodes to return
     maxDistance: maximum distance to point result nodes should have
     condition (not implemented): function to test node before it's added to the result list, e.g. test for view frustum
     */

    var i,
      result,
      bestNodes;

    bestNodes = new BinaryHeap(
      function ( e ) {
        return - e[ 1 ];
      }
    );

    function nearestSearch( node ) {
      var bestChild,
        dimension = node.depth % eleSize,
        ownDistance = metric( point, node.obj ),
        linearDistance = 0,
        otherChild,
        i,
        linearPoint = [];

      function saveNode( node, distance ) {
        bestNodes.push( [ node, distance ] );
        if ( bestNodes.size() > maxNodes ) {
          bestNodes.pop();
        }
      }

      for ( i = 0; i < eleSize; i += 1 ) {
        if ( i === node.depth % eleSize ) {
          linearPoint[ i ] = point[ i ];
        } else {
          linearPoint[ i ] = node.obj[ i ];
        }
      }

      linearDistance = metric( linearPoint, node.obj );

      // if it's a leaf
      if ( node.right === null && node.left === null ) {
        if ( bestNodes.size() < maxNodes || ownDistance < bestNodes.peek()[ 1 ] ) {
          saveNode( node, ownDistance );
        }
        return;
      }

      if ( node.right === null ) {
        bestChild = node.left;
      } else if ( node.left === null ) {
        bestChild = node.right;
      } else {
        if ( point[ dimension ] < node.obj[ dimension ] ) {
          bestChild = node.left;
        } else {
          bestChild = node.right;
        }
      }

      // recursive search
      nearestSearch( bestChild );
      if ( bestNodes.size() < maxNodes || ownDistance < bestNodes.peek()[ 1 ] ) {
        saveNode( node, ownDistance );
      }

      // if there's still room or the current distance is nearer than the best distance
      if ( bestNodes.size() < maxNodes || Math.abs( linearDistance ) < bestNodes.peek()[ 1 ] ) {
        if ( bestChild === node.left ) {
          otherChild = node.right;
        } else {
          otherChild = node.left;
        }
        if ( otherChild !== null ) {
          nearestSearch( otherChild );
        }
      }
    }
    if ( maxDistance ) {
      for ( i = 0; i < maxNodes; i += 1 ) {
        bestNodes.push( [ null, maxDistance ] );
      }
    }
    nearestSearch( self.root );
    result = [];
    for ( i = 0; i < maxNodes; i += 1 ) {
      if ( bestNodes.content[ i ][ 0 ] ) {
        result.push( [ bestNodes.content[ i ][ 0 ], bestNodes.content[ i ][ 1 ] ] );
      }
    }
    return result;
  };
};

/**
 * If you need to free up additional memory and agree with an additional O( log n ) traversal time you can get rid of "depth" and "pos" in Node:
 * Depth can be easily done by adding 1 for every parent (care: root node has depth 0, not 1)
 * Pos is a bit tricky: Assuming the tree is balanced (which is the case when after we built it up), perform the following steps:
 *   By traversing to the root store the path e.g. in a bit pattern (01001011, 0 is left, 1 is right)
 *   From buildTree we know that "median = Math.floor( plength / 2 );", therefore for each bit...
 *     0: amountOfNodesRelevantForUs = Math.floor( (pamountOfNodesRelevantForUs - 1) / 2 );
 *     1: amountOfNodesRelevantForUs = Math.ceil( (pamountOfNodesRelevantForUs - 1) / 2 );
 *        pos += Math.floor( (pamountOfNodesRelevantForUs - 1) / 2 );
 *     when recursion done, we still need to add all left children of target node:
 *        pos += Math.floor( (pamountOfNodesRelevantForUs - 1) / 2 );
 *        and I think you need to +1 for the current position, not sure.. depends, try it out ^^
 *
 * I experienced that for 200'000 nodes you can get rid of 4 MB memory each, leading to 8 MB memory saved.
 */
KDTree.prototype.Node = function ( obj, depth, parent, pos ) {
  this.obj = obj;
  this.left = null;
  this.right = null;
  this.parent = parent;
  this.depth = depth;
  this.pos = pos;
};

module.exports = KDTree;